{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，数组中的元素 <strong>互不相同</strong> 。返回该数组所有可能的子集（幂集）。</p>\n",
    "\n",
    "<p>解集 <strong>不能</strong> 包含重复的子集。你可以按 <strong>任意顺序</strong> 返回解集。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>[[],[0]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10</code></li>\n",
    "\t<li><code>-10 <= nums[i] <= 10</code></li>\n",
    "\t<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subsets](https://leetcode.cn/problems/subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subsets](https://leetcode.cn/problems/subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 状态压缩 + 子集\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    \n",
    "    def subsets(self, words: List[int]) -> List[List[int]]:\n",
    "        res = ['']\n",
    "        for i in words:\n",
    "            res = res + [i + word for word in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        #先处理 words\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "                # 统计具有相同模板的word有多少个，因为这里不涉及字母次数\n",
    "            freq[mask] += 1 \n",
    "\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):#求子集\n",
    "                mask = 1<< (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    def subsets(self,words):\n",
    "        res = [\"\"]\n",
    "        for i in words:\n",
    "            res = res + [ i+ word for word in res ]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    \n",
    "    def subsets(self, words: List[int]) -> List[List[int]]:\n",
    "        res = [\"\"]\n",
    "        for i in words:\n",
    "            res = res + [i + word for word in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        words_count = Counter(self.word_to_int(x) for x in words)\n",
    "        rst = [0] * len(puzzles)\n",
    "        for i in range(len(puzzles)):\n",
    "            puzzle_subsets = self.subsets(puzzles[i])\n",
    "            for puzzle_subset in puzzle_subsets:\n",
    "                rst[i] += words_count[puzzle_subset]\n",
    "        return rst\n",
    "        \n",
    "    def word_to_int(self, word: str) -> int:\n",
    "        rst = 0\n",
    "        for ch in word:\n",
    "            rst = rst | (1 << (ord(ch) - ord('a')))\n",
    "        return rst\n",
    "\n",
    "    def subsets(self, word: str) -> List[int]:\n",
    "        first_ch_int = 1 << (ord(word[0]) - ord('a'))\n",
    "        rst = []\n",
    "        for i in range(0, len(word)):\n",
    "            \n",
    "            for x in combinations(word[1:], i):\n",
    "                word_rst = first_ch_int\n",
    "                for x1 in x:\n",
    "                    word_rst = word_rst | (1 << (ord(x1) - ord('a')))\n",
    "                rst.append(word_rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        \n",
    "        def getComb(nList, res):\n",
    "            if res not in ans:\n",
    "                ans.append(res)\n",
    "            \n",
    "            for i, v in enumerate(nList):\n",
    "                getComb(nList[i+1:], res + [v])\n",
    "                \n",
    "        getComb(nums, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        ret = []\n",
    "        \n",
    "        def backtrack(nums, ret, add, start):\n",
    "            ret.append(add)\n",
    "            for i in range(start, len(nums)):\n",
    "                if i == start or nums[i] != nums[i - 1]:\n",
    "                    backtrack(nums, ret, add + [nums[i]], i + 1)\n",
    "        \n",
    "        nums.sort()\n",
    "        backtrack(nums, ret, [], 0)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        ans = [[]]\n",
    "        self.getSubset(nums, ans, 0, [])\n",
    "        return ans\n",
    "        \n",
    "    def getSubset(self, nums, ans, i, cur):\n",
    "        if i == len(nums):\n",
    "            return\n",
    "        # if i > 0 and nums[i] == nums[i-1]:\n",
    "        #     self.getSubset(nums, ans, i+1)\n",
    "        #     return\n",
    "        for j in range(i, len(nums)):\n",
    "            if j > i and nums[j] == nums[j-1]:\n",
    "                continue\n",
    "            cur.append(nums[j])\n",
    "            ans.append(cur.copy())\n",
    "            self.getSubset(nums, ans, j+1, cur)\n",
    "            cur.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "\n",
    "        sub_list_index = [[[i] for i in range(len(nums))]]\n",
    "\n",
    "        for sub_length in range(1, len(nums)):\n",
    "            curLength_sub = []\n",
    "            for j in range(len(sub_list_index[sub_length - 1])):\n",
    "                max_num = sub_list_index[sub_length - 1][j][-1]\n",
    "                for k in range(max_num + 1, len(nums)):\n",
    "                    cur_set = []\n",
    "                    cur_set.extend(sub_list_index[sub_length - 1][j])\n",
    "                    cur_set.extend([k])\n",
    "                    curLength_sub.append(cur_set)\n",
    "            sub_list_index.append(curLength_sub)\n",
    "\n",
    "        sub_list = []\n",
    "        for i in range(len(sub_list_index)):\n",
    "            for j in range(len(sub_list_index[i])):\n",
    "                cur_list = []\n",
    "                for k in range(len(sub_list_index[i][j])):\n",
    "                    cur_list.append(nums[sub_list_index[i][j][k]])\n",
    "                sub_list.append(cur_list)\n",
    "\n",
    "        sub_set = set()\n",
    "        for i in range(len(sub_list)):\n",
    "            # for j in range(len(sub_list_index[i])):\n",
    "            sub_set.add(tuple(sub_list[i]))\n",
    "\n",
    "        sub_list = []\n",
    "        for _ in range(len(sub_set)):\n",
    "            sub_list.append(list(sub_set.pop()))\n",
    "        sub_list.append([])\n",
    "\n",
    "        return sub_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        #print([1,2].sort())\n",
    "        list1=[]\n",
    "        final=[[]]\n",
    "        if nums==[]:return final\n",
    "        for i in nums:\n",
    "            i=[i]\n",
    "            \n",
    "            for j in range(len(final)):\n",
    "                a=final[j].copy()+i.copy()\n",
    "                a.sort()\n",
    "                #print(final[j],i ,a,list1)\n",
    "                if a not in list1:\n",
    "                    final.append(a)\n",
    "                    list1.append(a)\n",
    "                if i not in list1:\n",
    "                    final.append(i)\n",
    "                    list1.append(i)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        tmp = []\n",
    "        self.dfs(res, tmp, nums, 0)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, res, tmp, nums, start):\n",
    "        tmp.sort()\n",
    "        if tmp not in res:\n",
    "            res.append(tmp)\n",
    "        if start == len(nums):\n",
    "            return\n",
    "        for i in range(start, len(nums)):\n",
    "            self.dfs(res, tmp+[nums[i]], nums, i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            cres=res.copy()\n",
    "            for i in cres:\n",
    "                if (sorted(i+[num])) not in res:\n",
    "                    res.append(sorted(i+[num]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "        res=[[]]\n",
    "        for i in range(len(nums)):\n",
    "            res+=[subset+[nums[i]] for subset in res]\n",
    "\n",
    "        # 去重\n",
    "        dic={}\n",
    "        for x in res:\n",
    "            dic[str(x)]=0\n",
    "        result=[]\n",
    "        for i in dic.keys():\n",
    "            result.append(eval(i))# 字符串变list，tuple，表达式，神奇\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def huisu(nums,i,item,res):\n",
    "            if i >= len(nums):\n",
    "                return\n",
    "            item.append(nums[i])\n",
    "            print(i)\n",
    "            a=[]\n",
    "            for j in item:\n",
    "                a += [j]\n",
    "            a.sort()\n",
    "            if a not in res:\n",
    "\n",
    "                res.append(a)\n",
    "            huisu(nums,i+1,item,res)\n",
    "            item.pop(-1)\n",
    "            print('i=',i)\n",
    "            huisu(nums,i+1,item,res)\n",
    "        i=0\n",
    "        item=[]\n",
    "        res=[]\n",
    "        huisu(nums,i,item,res)\n",
    "        res.append([])\n",
    "        res.sort()\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        L = [[]]\n",
    "        L1 = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(L)):\n",
    "                L1 = L[j] + [nums[i]]\n",
    "                if L1 in L:\n",
    "                    L1 = []\n",
    "                    continue\n",
    "                else:\n",
    "                    L.append(L1)\n",
    "                    L1 = []\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        cache = [[]]\n",
    "        tmp_val = None\n",
    "        left = -1\n",
    "        for i in nums:\n",
    "            if i != tmp_val:\n",
    "                tmp_val = i\n",
    "                tmp_cache = cache.copy()\n",
    "                cache += [j + [i] for j in cache]\n",
    "            else:\n",
    "                for j, v in enumerate(tmp_cache):\n",
    "                    if v != cache[j]:\n",
    "                        left = j\n",
    "                        break\n",
    "                left = len(tmp_cache) if left == -1 else left\n",
    "                tmp_cache = cache.copy()\n",
    "                cache += [j+[i] for j in cache[left:]]\n",
    "                left = -1\n",
    "        return cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        dic = collections.Counter(nums)\n",
    "        res = [[]]\n",
    "        for i, v in dic.items():\n",
    "            temp = res.copy()\n",
    "            for j in res:\n",
    "                temp.extend(j+[i]*(k+1) for k in range(v))\n",
    "            res = temp\n",
    "            #print(res, i, v)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        if not nums:\n",
    "            return res\n",
    "        \n",
    "        def help_subset(curr, k, idx):\n",
    "            if len(curr) == k:\n",
    "                res.append(curr[:])\n",
    "                return\n",
    "            for i in range(idx, len(nums)):\n",
    "                if len(nums)-i < k-len(curr):\n",
    "                    break\n",
    "                if i > idx and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                curr.append(nums[i])\n",
    "                help_subset(curr, k, i+1)\n",
    "                curr.pop()\n",
    "        \n",
    "        nums.sort()\n",
    "        for k in range(1, len(nums)+1):\n",
    "            help_subset([], k, 0)\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)+1):\n",
    "            self.Backtracking(nums, i, 0, [], res)\n",
    "        return res\n",
    "    \n",
    "    def Backtracking(self, nums, length:int, index, cur, res):\n",
    "        if len(cur) == length:\n",
    "            if cur not in res:\n",
    "                res.append(cur[:])\n",
    "                return \n",
    "        for i in range(index, len(nums)):\n",
    "            cur.append(nums[i])\n",
    "            self.Backtracking(nums, length, i+1, cur, res)\n",
    "            cur.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        self.helper(res, nums, 0, [])\n",
    "        return res\n",
    "    \n",
    "    def helper(self, res, nums, index, path):\n",
    "        res.append(path)\n",
    "        for i in range(index, len(nums)):\n",
    "            if i > index and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            self.helper(res, nums, i+1, path+[nums[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "\n",
    "    def getChild(self, resChild: List[int], nums: List[int]):\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            resChild.append(nums[i])\n",
    "            self.getChild(resChild, nums[i+1:])\n",
    "            Solution.res.append(resChild.copy())\n",
    "            resChild.pop()\n",
    "\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        Solution.res = [[]]\n",
    "        self.getChild([], nums)\n",
    "        return Solution.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(i, nums, subset, subsets):\n",
    "\n",
    "\n",
    "    if i == len(nums):\n",
    "        sort_subset = tuple(sorted(subset))\n",
    "        subsets.add(sort_subset)\n",
    "        return\n",
    "    \n",
    "    subset.append(nums[i])\n",
    "    dfs(i+1, nums, subset, subsets)\n",
    "    subset.pop()\n",
    "    dfs(i+1, nums, subset, subsets)\n",
    "    \n",
    "    return\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        subsets = set()\n",
    "        dfs(0, nums, [], subsets)\n",
    "\n",
    "        return [list(subset) for subset in subsets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def backtrack(i,tmp):\n",
    "            res.append(tmp[:])\n",
    "            for j in range(i,n):\n",
    "                tmp.append(nums[j])\n",
    "                backtrack(j+1,tmp)\n",
    "                tmp.pop()\n",
    "        \n",
    "        backtrack(0,[])\n",
    "        res2 = []\n",
    "        for i in res:\n",
    "            if sorted(i) not in res2:\n",
    "                res2.append(sorted(i))\n",
    "        return res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def dfs(tmp, start):\n",
    "\n",
    "            res.append(tmp)               # 要用 列表的 引用，否者更新 tmp 会改变 res 中元素的值\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "\n",
    "                dfs(tmp + [nums[i]], i+1)\n",
    "\n",
    "        res = []\n",
    "        dfs([], 0)\n",
    "\n",
    "        return [ list(element) for element in set([tuple(sorted(ele)) for ele in res]) ]\n",
    "\n",
    "'''\n",
    "        result = []\n",
    "        nums.sort()\n",
    "\n",
    "        def dfs(tmp, start):\n",
    "\n",
    "            result.append(tmp[:])\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "\n",
    "                if i > start and nums[i] == nums[i-1]:  \n",
    "                    continue\n",
    "\n",
    "                tmp.append(nums[i])\n",
    "                dfs(tmp, i+1)\n",
    "                tmp.pop()\n",
    "\n",
    "        dfs([], 0)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "[1,2,2,2]\n",
    "\n",
    "[[],[1],[1,2],[1,2,2],[1,2,2,2],[2],[2,2],[2,2,2]]\n",
    "\n",
    "              []              backtrack([], 0)\n",
    "     i=0     i=1       i=2    start = 0, i in [0,1,2]  for i in range(0,3)\n",
    "     [1]     [2]       [2]\n",
    "  [1,2]                       start = 1, i in [1,2]    for i in range(1,3)\n",
    "[1,2,3]                       start = 2, i in [2]      for i in range(2,3)\n",
    "\n",
    "https://leetcode-cn.com/problems/subsets-ii/solution/hui-su-suan-fa-by-powcai-6/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "# 刚开始我们只有空集一个答案，循环所有可能的数字，每次循环我们对当前答案的每一种情况考虑加入从1到上限次该数字并更新答案即可\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        result, track = [], []\n",
    "        nums.sort()\n",
    "        self.backtrack(result, 0, nums, track)\n",
    "        return result\n",
    "\n",
    "    def backtrack(self, result, start, num, track):\n",
    "        result.append(track[:])\n",
    "        print('此时的结果为',result)\n",
    "        for i in range(start, len(num)):\n",
    "            if i > start and num[i] == num[i-1]:\n",
    "                continue\n",
    "\n",
    "            track.append(num[i])\n",
    "            self.backtrack(result, i+1, num, track)\n",
    "            track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        def bt(res, path, start, nums, last_add):\n",
    "            if start == len(nums):\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            \n",
    "            bt(res, path, start+1, nums, last_add=False)\n",
    "\n",
    "            if not(start > 0 and nums[start] == nums[start-1] and last_add == False):\n",
    "                path.append(nums[start])\n",
    "                bt(res, path, start+1, nums, last_add=True)\n",
    "                path.pop()\n",
    "            \n",
    "        res = []\n",
    "        path = []\n",
    "        start = 0\n",
    "        nums.sort()\n",
    "        bt(res, path, start, nums, last_add=False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        answer = []\n",
    "        answers = []\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        def backtracking(index):\n",
    "            answers.append(answer[:])\n",
    "            \n",
    "            for i in range(index, len(nums)):\n",
    "                if i > index and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                \n",
    "                answer.append(nums[i])\n",
    "                backtracking(i+1)\n",
    "                answer.pop()\n",
    "            pass\n",
    "        \n",
    "        backtracking(0)\n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res, length, tmp = [], len(nums), []\n",
    "        def traverse(idx: int):\n",
    "            if idx == length:\n",
    "                res.append(tmp.copy())\n",
    "                return\n",
    "\n",
    "            tmp.append(nums[idx])\n",
    "            \n",
    "            traverse(idx + 1)\n",
    "            tmp.pop()\n",
    "            # jump over the duplicate\n",
    "            while idx + 1 < length and nums[idx] == nums[idx + 1]:\n",
    "                idx += 1\n",
    "            traverse(idx + 1)\n",
    "\n",
    "        traverse(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res, length, tmp = [], len(nums), []\n",
    "        def traverse(idx: int):\n",
    "            if idx == length:\n",
    "                res.append(tmp.copy())\n",
    "                return\n",
    "\n",
    "            tmp.append(nums[idx])\n",
    "            # if tmp not in res:\n",
    "            traverse(idx + 1)\n",
    "            tmp.pop()\n",
    "            # if tmp not in res:\n",
    "            while idx + 1 < length and nums[idx] == nums[idx + 1]:\n",
    "                idx += 1\n",
    "            traverse(idx + 1)\n",
    "\n",
    "        traverse(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = set()\n",
    "        def deepin(i, parts):\n",
    "            if i>=len(nums):\n",
    "                res.add(parts)\n",
    "                return\n",
    "            deepin(i+1, parts)\n",
    "            deepin(i+1, parts+str(nums[i])+',')\n",
    "        deepin(0, \"\")\n",
    "\n",
    "        res = [x.split(\",\") for x in list(res)]\n",
    "        res = [list(filter(lambda x: x!=\"\", x)) for x in res]\n",
    "        res = sorted([sorted([int(y) for y in x]) for x in res])\n",
    "\n",
    "        res_ = []\n",
    "        i = 0\n",
    "        while i<len(res):\n",
    "            while i+1<len(res) and res[i+1] == res[i]:\n",
    "                i += 1\n",
    "            res_.append(res[i])\n",
    "            i += 1\n",
    "        return res_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        from collections import defaultdict\n",
    "        # nums = [4,4,4,1,4]\n",
    "        ans = []\n",
    "        ans_statistic = []\n",
    "        def statistic(n):\n",
    "            tmp = defaultdict(int)\n",
    "            for i in n:\n",
    "                tmp[i] += 1\n",
    "            return tmp\n",
    "\n",
    "        def search(i,tmp):\n",
    "            tmp_s = statistic(tmp)\n",
    "            if (tmp not in ans) and (tmp_s not in ans_statistic):\n",
    "                ans.append(tmp)\n",
    "                ans_statistic.append(tmp_s)\n",
    "\n",
    "            for j in range(i,len(nums)):\n",
    "                search(j+1,tmp+[nums[j]])\n",
    "            return\n",
    "        \n",
    "        search(0,[])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        def dfs(start, path):\n",
    "            res.append(path[:])\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > start and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                dfs(i+1, path)\n",
    "                path.pop()\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        used = [0]*n\n",
    "        def backTracking(nums,res,path,startIndex,used):\n",
    "            res.append(path[:])\n",
    "            for i in range(startIndex,n):\n",
    "                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = 1\n",
    "                backTracking(nums,res,path,i+1,used)\n",
    "                used[i] = 0\n",
    "                path.pop()\n",
    "        backTracking(nums,res,[],0,used)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        nums = sorted(nums)\n",
    "        def back_track(index):\n",
    "            temp = tmp.copy()\n",
    "            ans.append(temp)\n",
    "            if index == len(nums):\n",
    "                return \n",
    "            for i in range(index, len(nums)):\n",
    "                if i > index and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                tmp.append(nums[i])\n",
    "                back_track(i + 1)\n",
    "                tmp.pop()\n",
    "        back_track(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        if not nums:\n",
    "            return ans\n",
    "        \n",
    "        def getSubsets(start, cur):\n",
    "            ans.append(cur)\n",
    "                \n",
    "            for i in range(start, len(nums)):\n",
    "                getSubsets(i+1, cur + [nums[i]])\n",
    "                           \n",
    "        getSubsets(0, [])\n",
    "                           \n",
    "        return ans\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        n = len(nums)\n",
    "        ret = [[]]\n",
    "        for i in range(n):\n",
    "            m = len(ret)\n",
    "            for j in range(m):\n",
    "                t = ret[j].copy()\n",
    "                t.append(nums[i])\n",
    "                ret.append(t)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        def subsetsHelper(nums, pointer):\n",
    "            if pointer >= len(nums):\n",
    "                return [[]]\n",
    "            tmp = subsetsHelper(nums, pointer + 1)\n",
    "            res = []\n",
    "            for i in tmp:\n",
    "                res.append(i[:])\n",
    "                i.append(nums[pointer])\n",
    "                res.append(i[:])\n",
    "            return res\n",
    "        return subsetsHelper(nums, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        for i in range(len(nums)+1):\n",
    "           ans.extend(list(itertools.combinations(nums, i)))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        for i in range(len(nums)+1):\n",
    "           ans.extend(list(set(itertools.combinations(nums, i))))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        for n in nums:\n",
    "                res = res+[i+[n] for i in res if i+[n] not in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        for i in range(2**length):\n",
    "            result1 = []\n",
    "            for j in range(length):\n",
    "                if (i >> j) % 2 == 1:\n",
    "                    print('i=',i,'j=',j)\n",
    "                    result1.append(nums[j])\n",
    "            result.append(result1)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        for i in range(2**length):\n",
    "            result1 = []\n",
    "            for j in range(length):\n",
    "                if (i >> j) % 2 == 1:\n",
    "                    print('i=',i,'j=',j)\n",
    "                    result1.append(nums[j])\n",
    "            result.append(result1)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        N = 2**len(nums)\n",
    "        sets = [[] for i in range(N)]\n",
    "        for i, num in enumerate(nums):\n",
    "            gap = 2**i\n",
    "            for j in range(0+gap, N, gap*2):\n",
    "                for k in range(gap):\n",
    "                    sets[j+k].append(num)\n",
    "        return sets\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(res)):\n",
    "                new = copy.deepcopy(res[j])\n",
    "                new.append(nums[i])\n",
    "                res.append(new)\n",
    "        return(res)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return [[]]\n",
    "        \n",
    "        ans = [[]]\n",
    "        for i in range(len(nums)):\n",
    "            ans.append([nums[i]])\n",
    "            cur_res = self.subsets(nums[i + 1:])[1:]\n",
    "            for j in cur_res:\n",
    "                ans.append([nums[i]] + j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        import itertools\n",
    "\n",
    "        ls = [[], nums]\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            for item in itertools.combinations(nums, i):\n",
    "                ls.append(list(item))\n",
    "        return ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\n",
    "        res = []\n",
    "        def backtracking(tmp, n):\n",
    "            if n == len(nums):\n",
    "                res.append(list(tmp))\n",
    "            else:\n",
    "                backtracking(tmp, n+1)\n",
    "                tmp += (nums[n],)\n",
    "                backtracking(tmp, n+1)\n",
    "        backtracking((), 0)\n",
    "        return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    a = [1,2,3]\n",
    "    b = Solution().subsets(a)\n",
    "    print(b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import copy\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums)==0:\n",
    "            return []\n",
    "        else:\n",
    "            n =[[nums[0]],[]]\n",
    "        for i in range(1,len(nums)):\n",
    "            h =[]\n",
    "            for j in range(2):\n",
    "                for k in range(len(n)):\n",
    "                    if j ==0:\n",
    "                        x = copy.deepcopy(n[k])\n",
    "                        x.append(nums[i])\n",
    "                        h.append(x)\n",
    "                    else:\n",
    "                        h.append(n[k])\n",
    "            n = h\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = [[]]\n",
    "        for num in nums:\n",
    "            c = []\n",
    "            for ls in result:\n",
    "                a = ls[:]\n",
    "                a.append(num)\n",
    "                c.append(a)\n",
    "            result = result + c\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        \n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        for i in range(len(nums)+1):\n",
    "            self.combination(nums, 0, i, [])\n",
    "        return self.res\n",
    "    \n",
    "    def combination(self, nums, start, k, res):\n",
    "        if len(res) == k:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "\n",
    "        if len(res) > k:\n",
    "            return \n",
    "        for i in range(start, len(nums)):\n",
    "            e = nums[i]\n",
    "            res.append(e)\n",
    "            self.combination(nums, i+1, k, res.copy())\n",
    "            res.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def helper(i, tmp):\n",
    "            res.append(tmp)\n",
    "            for j in range(i, n):\n",
    "                helper(j + 1,tmp + [nums[j]] )\n",
    "        helper(0, [])\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        l = nums\n",
    "        n = len(l)\n",
    "        m={}\n",
    "        for i in range(2**n):\n",
    "            t=[0 for i in range(n)]\n",
    "            j = i\n",
    "            k = 0\n",
    "            while(j>0):\n",
    "                t[n-k-1] = j%2\n",
    "                k+=1\n",
    "                j=int(j/2)\n",
    "            #print(i, t)\n",
    "            o=[]\n",
    "            for j in range(len(t)):\n",
    "                if t[j]:\n",
    "                    o.append(str(l[j]))\n",
    "            #print(o)\n",
    "            if len(o)>0:\n",
    "                m[','.join(o)]=True\n",
    "        m = [i.split(',') for i in m.keys()]\n",
    "        m = [ [int(j) for j in i] for i in m]\n",
    "        m.append([])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return [[]]\n",
    "        if len(nums) == 1:\n",
    "            return [nums, []]\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            temp = nums[:]\n",
    "            temp.pop(i)\n",
    "            res.extend(self.subsets(temp))\n",
    "        r = [nums]\n",
    "        for rr in res:\n",
    "            if rr not in r:\n",
    "                r.append(rr)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def huisu(tmp, length, index, res, nums): \n",
    "            # 符合当前长度\n",
    "            if len(tmp) == length:\n",
    "                res.append(tmp[:]) # tmp=[1,2] , tmp[:]为复制一份的新[1,2]\n",
    "                print(res)\n",
    "                return\n",
    "            # 寻找中\n",
    "            for i in range(index, len(nums)):\n",
    "                tmp += [nums[i]]\n",
    "                huisu(tmp, length, i + 1, res, nums)  # i+1为了从下一个元素index开始for\n",
    "                tmp.pop() # tmp.pop 会改res里面的。=[]就不会改res里面的，但=[]再长度=2时需要pop，不能全清空\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(nums) + 1):  # 长度0 1 2 3\n",
    "            huisu(tmp=[], length=i, index=0, res=res, nums=nums)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums):\t\t\n",
    "        if not nums:\n",
    "            return []\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def helper(idx, temp_list):\n",
    "            res.append(temp_list)\n",
    "            for i in range(idx, n):\n",
    "                helper(i + 1, temp_list + [nums[i]])\n",
    "\n",
    "        helper(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return [nums]\n",
    "        \n",
    "        res:list[list] = []\n",
    "\n",
    "        def backtracing(path: list, nums: list[list], start_index: int) -> None:\n",
    "            res.append(path[:])\n",
    "            if start_index >= len(nums):\n",
    "                return\n",
    "            \n",
    "            for i in range(start_index, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtracing(path, nums, i + 1)\n",
    "                path.pop()\n",
    "        \n",
    "        backtracing([], nums, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "    # 动态规划的思想\n",
    "        # res=[[]]\n",
    "        # for num in nums:\n",
    "        #     # 外层循环遍历每一个元素\n",
    "        #     for subset in res[:]:\n",
    "        #         # 内层循环遍历结果列表中的每一个子列表\n",
    "        #         # 将其与外层正在遍历的那个元素相连\n",
    "        #         res.append(subset + [num])\n",
    "        # return res\n",
    "\n",
    "    # 位运算，二进制（不太好理解）\n",
    "        # size = len(nums)\n",
    "        # n = 1 << size  # n就是得到的子集个数2^3=8\n",
    "        # res = []\n",
    "        # for i in range(n):  # 遍历每个n，到不了n\n",
    "        #     cur = []\n",
    "        #     for j in range(size):\n",
    "        #         if (i >> j) & 1:\n",
    "        #             cur.append(nums[j])\n",
    "        #     res.append(cur)\n",
    "        # return res \n",
    "\n",
    "    # 回溯\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def helper(i, temp):\n",
    "            res.append(temp)\n",
    "            for j in range(i, n):\n",
    "                helper(j + 1, temp + [nums[j]])\n",
    "        helper(0, [])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        t = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                res.append(t[:])\n",
    "                return\n",
    "            t.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            t.pop()\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        def binary_bit(nums):\n",
    "            res = []\n",
    "            for i in range(1 << len(nums)):\n",
    "                sub = []\n",
    "                for j in range(len(nums)):\n",
    "                    if (i >> j) & 1 == 1:\n",
    "                        sub.append(nums[j])      \n",
    "                res.append(sub)\n",
    "            return res\n",
    "        # res = binary_bit(nums)\n",
    "\n",
    "        def enumerate(nums):\n",
    "            res = [[]]\n",
    "            for n in nums:\n",
    "                size = len(res)\n",
    "                for i in range(size):\n",
    "                    new_sub = list(res[i])\n",
    "                    new_sub.append(n)\n",
    "                    res.append(new_sub)\n",
    "            return res\n",
    "        # res = enumerate(nums)\n",
    "\n",
    "        def enumerate_recursion(nums, i, res):\n",
    "            if i == len(nums):\n",
    "                return res\n",
    "            for j in range(len(res)):\n",
    "                new_sub = list(res[j])\n",
    "                new_sub.append(nums[i])\n",
    "                res.append(new_sub)\n",
    "            return enumerate_recursion(nums, i + 1, res)\n",
    "        # res = enumerate_recursion(nums, 0, [[]])\n",
    "\n",
    "        \n",
    "        def dfs2(start, subset):\n",
    "            res.append(subset)\n",
    "            for i in range(start, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                dfs(i+1, subset[:])\n",
    "                subset.pop()\n",
    "        # res = []\n",
    "        # dfs2(0, [])\n",
    "        def dfs(start, subset, res):\n",
    "            res.append(subset[:])\n",
    "            for i in range(start, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                res = dfs(i + 1, subset, res)\n",
    "                subset.pop()\n",
    "            return res\n",
    "        # res = dfs(0, [], [])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def binary_tree_inOrder(i, subset, res):\n",
    "            if i >= len(nums):\n",
    "                return res\n",
    "            res = binary_tree_inOrder(i+1, subset[:], res)\n",
    "            subset.append(nums[i])\n",
    "            res.append(subset)\n",
    "            res = binary_tree_inOrder(i+1, subset[:], res)\n",
    "            return res\n",
    "        # res = binary_tree_inOrder(0, [], [[]])\n",
    "        def binary_tree_inOrder2(i, subset):\n",
    "            if i >= len(nums):\n",
    "                return\n",
    "            binary_tree_inOrder2(i+1, subset[:])\n",
    "            subset.append(nums[i])\n",
    "            res.append(subset)\n",
    "            node_num = len(res)-1\n",
    "            print('res {}: level: {}, '.format(node_num, i), subset)\n",
    "            binary_tree_inOrder2(i+1, subset[:])\n",
    "        # res = [[]]\n",
    "        # binary_tree_inOrder2(0, [])\n",
    "        # print(\"in-order:   \", res)\n",
    "\n",
    "\n",
    "        def binary_tree_preOrder(i, subset, res):\n",
    "            if i >= len(nums):\n",
    "                return res\n",
    "            res.append(subset)\n",
    "            res = binary_tree_preOrder(i+1, subset[:], res)\n",
    "            subset.append(nums[i])\n",
    "            res = binary_tree_preOrder(i+1, subset[:], res)\n",
    "            return res\n",
    "        # res = binary_tree_preOrder(0, [], [[]])\n",
    "        # print(\"pre-order:\", res)\n",
    "        def binary_tree_preOrder2(i, subset):\n",
    "            if i >= len(nums):\n",
    "                return\n",
    "            res.append(subset)\n",
    "            node_num = len(res)-1\n",
    "            print('res {}: level: {}, NEW '.format(node_num, i), subset)\n",
    "            binary_tree_preOrder2(i+1, subset[:])\n",
    "            subset.append(nums[i])\n",
    "            print('res {}: level: {}, MODIFIED '.format(node_num, i), subset)\n",
    "            binary_tree_preOrder2(i+1, subset[:])\n",
    "        # res = [[]]\n",
    "        # binary_tree_preOrder2(0, [])\n",
    "        # print(\"pre-order: \", res)\n",
    "\n",
    "        \n",
    "        def binary_tree_postOrder2(i, subset):\n",
    "            if i >= len(nums):\n",
    "                return\n",
    "            binary_tree_postOrder2(i+1, subset[:])\n",
    "            subset.append(nums[i])\n",
    "            binary_tree_postOrder2(i+1, subset[:])\n",
    "            res.append(subset)\n",
    "            node_num = len(res)-1\n",
    "            print('res {}: level: {}, NEW '.format(node_num, i), subset)\n",
    "        # res = [[]]\n",
    "        # binary_tree_postOrder2(0, [])\n",
    "        # print(\"post-order:\", res)\n",
    "        \n",
    "        res = []\n",
    "        def dfs3(i, subset):\n",
    "            res.append(subset)\n",
    "            if i == len(nums):\n",
    "                return\n",
    "            for j in range(i, len(nums)):\n",
    "                subset.append(nums[j])\n",
    "                dfs3(j+1, subset[:])\n",
    "                subset.pop()\n",
    "        dfs3(0, [])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [set()]\n",
    "        add_set = [set()]\n",
    "        finish = False\n",
    "        # 时间复杂度O(2^n * n)，空间复杂度为O(n)，主要为new_add_set占用\n",
    "        while not finish:\n",
    "            new_add_set = []\n",
    "            for s in add_set:\n",
    "                if finish:\n",
    "                    break\n",
    "                for num in nums:\n",
    "                    if num not in s:\n",
    "                        new_s = s | set([num])   # 取并集\n",
    "                        if new_s not in new_add_set:\n",
    "                            new_add_set.append(new_s) \n",
    "                            if len(new_s) == len(nums):\n",
    "                                finish = True\n",
    "                                break\n",
    "            add_set = new_add_set\n",
    "            res += new_add_set\n",
    "\n",
    "        l = [list(s) for s in res]\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = 2 ** len(nums)\n",
    "        result = list()\n",
    "        for i in range(n):\n",
    "            temp = i\n",
    "            index = len(nums) - 1\n",
    "            temp_list = list()  \n",
    "            while temp != 0:\n",
    "                if temp % 2 == 1:\n",
    "                    temp_list.append(nums[index])\n",
    "                index -= 1\n",
    "                temp //= 2\n",
    "            result.append(temp_list)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.path = []\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtracking(nums, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtracking(self, nums, startIndex):\n",
    "        self.res.append(self.path[:])\n",
    "        if startIndex >= len(nums):\n",
    "            return \n",
    "        for i in range(startIndex, len(nums)):\n",
    "            self.path.append(nums[i])\n",
    "            self.backtracking(nums, i + 1)\n",
    "            self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets0(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            \n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "\n",
    "            dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "    def subsets1(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 位运算, 把每个数字的值当做集合 -10 <= nums[i] <= 10\n",
    "        s = 0\n",
    "        offset = 10\n",
    "        for num in nums:\n",
    "            s |= 1 << (num + offset)\n",
    "        \n",
    "        ans = []\n",
    "        sub = s\n",
    "        while True:\n",
    "            cur = sub\n",
    "            a = []\n",
    "            for i in range(sub.bit_length()):\n",
    "                if cur & 1: \n",
    "                    a.append(i-offset)\n",
    "                cur = cur >> 1 \n",
    "            ans.append(a)\n",
    "            sub = (sub-1) & s\n",
    "            if sub == s:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 在不在当做集合 1 <= nums.length <= 10\n",
    "        ans = []\n",
    "        for x in range(2 ** len(nums)):\n",
    "            a = []\n",
    "            for i in range(x.bit_length()):\n",
    "                #if x & (1 << i):\n",
    "                if (x >> i) & 1:\n",
    "                    a.append(nums[i])\n",
    "            ans.append(a)\n",
    "        return ans\n",
    "    \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
